package leetcode.pre100;


/**
 * 求一个数的开方。误差在error
 *
 * @date 2020/4/2 13:54
 */
public class Code69_Sqrt2 {
    public static void main(String[] args) throws InterruptedException {
        double error = 1e-6;
        System.out.println(sqrt(2, error));
        System.out.println(sqrt2(2, error));
        System.out.println(sqrt(4, error));
        System.out.println(sqrt2(4, error));
        System.out.println(sqrt(0.01, error));
        System.out.println(sqrt2(0.01, error));
        System.out.println(sqrt(8, error));
        System.out.println(sqrt2(8, error));

    }

    public static double sqrt(double n, double error) {
        if (n <= 0) return n == 0 ? 0 : -1;
        //采用二分法
        double left = n > 1 ? 1 : n;
        double right = n > 1 ? n : 1;
        while (left <= right) {
            double mid = (left + right) / 2;
            double temp = mid * mid;
            //TODO 这里应该是temp根号误差，不是平方后的
            if (Math.abs(temp - n) <= error) {
                return mid;
            }
            if (temp - n > 0) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return -1;
    }

    /**
     * 牛顿迭代
     * https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/
     *
     * @param n
     * @param error
     * @return
     */
    public static double sqrt2(double n, double error) {
        double x = n;
        while (x * x > n && Math.abs(x * x - n) >= error) {
            x = (x + n / x) / 2;
        }
        return x;
    }


}
